package com.li.algorithm.leetcode.hot100;

import java.util.*;

public class Test11 {

    /**
     * 使用优先级队列作为窗口容器（自动从大到小排序）
     * 队列中同时存储值和下标，方便将窗口排出的元素移除
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        //优先级队列
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] pair1, int[] pair2) {
                //TODO: 值是否相等？ 1.根据值排序，2.根据下标排序
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });

        //前k个元素，构成第一个区间
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }

        result[0] = pq.peek()[0];

        for (int i = k; i < nums.length; i++) {
            pq.offer(new int[]{nums[i], i});
            //移除非窗口内的元素
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            //队首元素为区间最大值
            result[i-k+1] = pq.peek()[0];
        }
        return result;
    }


    /**
     * 单调队列存储窗口信息（只存储有价值的下标值，及时将无价值的、无效的下标值移出队列）
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        //双端队列
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        //在一个窗口中  i<j, nums[i] < nums[j]，从这两个元素同时出现在窗口中开始， i 是无价值的，j 是有价值的
        //记录窗口中所有“有价值”的下标放入队列中
        //这个“有价值的”队列中下标上的值是单调递减的
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        result[0] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            //每次加入新元素时
            //将所有小于当前值的下标出队，再将当前下标放入队尾，保证“有价值”队列
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //判断当前队首是否已被窗口移除，移除则出队
            if (deque.peekFirst() <= (i - k)) {
                deque.pollFirst();
            }
            result[i-k+1] = nums[deque.peekFirst()];
        }
        return result;
    }


        public static void main(String[] args) {
        Test11 test11 = new Test11();
        int[] res = test11.maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}
/**、
 * 方法1：
 * TODO:遍历第一个区间[0,k]，记录最大值max及第二大的值sec
 * TODO:滑动窗口，每次移除第一个元素，加入新元素
 * TODO:判断最大值max是否为被移除的区间第一个元素
 *  如果是，将新元素与sec比较，得到当前新区间的最大值
 *  如果不是，将新元素与max比较，得到当前新区间的最大值
 * TODO:问题：如何更新sec？
 *
 *
 * 方法2：
 * 在遍历的过程中可以确定前面区间中的最大值
 * //TODO:每一个点的区间最大值，在后面 k-1 次的遍历中
 * //TODO: i点的最大值为 [i, i+(k-1)] 的最大值
 * //TODO: i点的最大值在遍历到 i+(k-1) 的时候才知道
 * //TODO: 如何记录每段区间的最大值？
 */